<!DOCTYPE html>
<html lang="zh">

<head>
  <meta charset="utf-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1">
  <title>
    
    线性表 - DSRBLOG
    
  </title>
  

  
  
  <link href="atom.xml" rel="alternate" title="DSRBLOG" type="application/atom+xml">
  <link rel="stylesheet" href="asset/css/style.min.css">
  <link rel="stylesheet" href="asset/css/doc.css">
  <script src="asset/app.js"></script>


</head>

<body> <section class="ct-body">
	<div class="container">
		<div class="columns is-variable bd-klmn-columns is-4 is-centered">
			<div class="column is-four-fifths">
				<div class="post-body single-content">
					
					<h1 class="title">
						线性表
					</h1>


					<div class="media">
						
						
						<div class="media-content">
							<div class="content">
								<p>
									<span class="date">2022/02/21 13:44 下午</span>
									

									

									<br />
									<span class="tran-tags">Tags:</span>&nbsp;
									
									<a class="tag is-link is-light">#数据结构与算法</a>
									

								</p>
							</div>
						</div>

					</div>
				</div>
				<article class="markdown-body single-content">
					<h2><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%80%BB%E8%BE%91%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的逻辑结构</h2>
<h3><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的定义</h3>
<p>若结构是非空有限集，则有且仅有一个开始结点和一个终端节点，并且所有节点都最多只有一个直接前驱和一个直接后继</p>
<p>可表示为：(<strong>a<sub>1</sub></strong>, a<sub>2</sub>, ..., <strong>a<sub>i-1</sub></strong>, a<sub>i</sub>, <strong>a<sub>i+1</sub></strong>, ..., <strong>a<sub>n</sub></strong>)</p>
<p><strong>a<sub>1</sub>：</strong> 线性起点<br />
<strong>a<sub>i-1</sub>：</strong> a<sub>i</sub>的直接前驱<br />
<strong>a<sub>i+1</sub>：</strong> a<sub>i</sub>的直接后继<br />
<strong>a<sub>n</sub>：</strong> 线性终点，<code>n</code>为元素总个数，即表长，<code>n = 0</code>时称为空表</p>
<h3><a id="%E7%BA%BF%E6%80%A7%E7%BB%93%E6%9E%84%E7%9A%84%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性结构的特点</h3>
<ul>
<li>只有一个首结点和尾结点</li>
<li>除首尾结点外，其他结点只有一个直接前驱和一个直接后继</li>
</ul>
<p>线性结构包括线性表、堆栈、队列、字符串、数组等，其中最典型、最常用的是<strong>线性表</strong></p>
<h3><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E7%B1%BB%E5%9E%8B%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的类型定义</h3>
<p>线性表是一个相当灵活的数据结构，其长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可以进行插入和删除等操作</p>
<h4><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E6%8A%BD%E8%B1%A1%E6%95%B0%E6%8D%AE%E7%B1%BB%E5%9E%8B%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的抽象数据类型定义</h4>
<p><img src="http://dsr213.cn:8000/i/2022/03/13/1647112429_1_1.png" alt="16470205046369" /></p>
<h2><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%A4%BA%E5%92%8C%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的顺序表示和实现</h2>
<h3><a id="%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E8%A1%A8%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序表的表示</h3>
<h4><a id="%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序表示</h4>
<p>线性表的顺序表示，通常称这种存储结构的线性表为<strong>顺序表</strong>，也称作线性表的<strong>顺序存储结构</strong>或<strong>顺序映像</strong>，即讨论了数据的逻辑结构，也讨论了数据的物理结构</p>
<h5><a id="%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E5%AE%9A%E4%B9%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序存储定义</h5>
<p>把<strong>逻辑上相邻</strong>的数据元素存储在<strong>物理上相邻</strong>的存储单元中的存储结构</p>
<h5><a id="%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E6%96%B9%E6%B3%95" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序存储方法</h5>
<p>用一组地址连续的存储单元一次存储线性表的元素，可通过数组<code>V[n]</code>来实现</p>
<h4><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E5%AD%98%E5%82%A8%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的存储特点</h4>
<ul>
<li>逻辑上相邻的数据元素，其物理上也相邻</li>
<li>若已知表中首元素在存储器中的位置，则其他元素存放位置亦可求出（利用数组下标）</li>
</ul>
<p>设首元素<strong>a<sub>1</sub></strong> 的存放地址为<strong>LOC(a<sub>1</sub>)</strong>（称为首地址），设每个元素占用 存储空间（地址长度）为L字节，则表中任意数据元素的存放地址为：</p>
<p>  LOC(a<sub>i</sub>) = LOC(a<sub>1</sub>) + L * (i-1)</p>
<h4><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E5%8A%A8%E6%80%81%E5%88%86%E9%85%8D%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的动态分配顺序存储结构</h4>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#define LIST_INIT_SIZE 100
#define LISTINCREAMENT 10
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;

typedef struct
{
    ElemType *elem; //表基址
    int length;     //表长（特指元素个数）
    int listsize;   //表当前存储容量（字节数）
} SqList;

void InitList(SqList *L);
void DestroyList(SqList *L);
void ClearList(SqList *L);

Status ListEmpty(SqList L);
int ListLength(SqList L);
Status GetElem(SqList L, int i, ElemType *e);
int LocateElme(SqList L, ElemType e);

Status PreElem(SqList L, ElemType cur_e, ElemType *pre_e);
Status NextElem(SqList L, ElemType cur_e, ElemType *next_e);

int main()
{
    SqList L;
    InitList(&amp;L);
    int i = 1;

    printf(&quot;%d&quot;, GetElem(L, i, L.elem));
    DestroyList(&amp;L);

    return 0;
}

void InitList(SqList *L) //初始化当前表
{
    L-&gt;elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L-&gt;elem)
    {
        printf(&quot;初始化失败&quot;);
        return;
    }
    L-&gt;length = 0;
    L-&gt;listsize = LIST_INIT_SIZE;
}

void DestroyList(SqList *L) //销毁当前表
{
    free(L-&gt;elem);
    L-&gt;elem = NULL;
    L-&gt;length = 0;
    L-&gt;listsize = 0;
}

void ClearList(SqList *L) //清空当前表
{
    L-&gt;length = 0;
}

Status ListEmpty(SqList L) //判断当前表是否为空
{
    if (L.length == 0)
        return TRUE;
    return FALSE;
}

int ListLength(SqList L) //求当前表长度
{
    return L.length;
}

Status GetElem(SqList L, int i, ElemType *e) //获取当前表中序号为i的元素值
{
    if (i &lt; 1 || i &gt; L.length)
    {
        printf(&quot;指定位置有误\n&quot;);
        return FALSE;
    }
    e = L.elem + i - 1;
    return TRUE;
}

int LocateElme(SqList L, ElemType e) //在当前表中查找对应元素的位置
{
    int i = 1;
    ElemType *p = L.elem;
    while (i &lt;= L.length &amp;&amp; *p != e)
    {
        i++;
        p++;
    }
    if (i &lt;= L.length)
        return i;
    return FALSE;
}

Status PreElem(SqList L, ElemType cur_e, ElemType *pre_e) //寻找指定元素的前驱（首节点无前驱）
{
    int i = 1;
    ElemType *p = L.elem;
    while (i &lt;= L.length &amp;&amp; *p != cur_e)
    {
        i++;
        p++;
    }
    if (i &lt;= L.length)
    {
        if (i == 1)
            return FALSE;
        else
        {
            pre_e = L.elem + i - 2;
            return TRUE;
        }
    }
    return FALSE;
}

Status NextElem(SqList L, ElemType cur_e, ElemType *next_e) //寻找指定元素的前驱（尾节点无后继）
{
    int i = 1;
    ElemType *p = L.elem;
    while (i &lt; L.length &amp;&amp; *p != cur_e)
    {
        i++;
        p++;
    }
    if (i &lt; L.length)
    {
        next_e = L.elem + i;
        return TRUE;
    }
    return FALSE;
}
</code></pre>
<h3><a id="%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序表的实现</h3>
<h4><a id="%E6%8F%92%E5%85%A5%E5%85%83%E7%B4%A0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>插入元素</h4>
<p>从后往前将所有元素依次向后移动一位，直到将新的元素插入到指定位置</p>
<h4><a id="%E5%88%A0%E9%99%A4%E5%85%83%E7%B4%A0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>删除元素</h4>
<p>从前往后操作元素，当删除指定元素后，该元素之后的所有元素依次向前移动</p>
<h4><a id="%E9%81%8D%E5%8E%86%E5%85%83%E7%B4%A0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>遍历元素</h4>
<p>从前往后依次输入每个元素</p>
<h4><a id="%E7%A4%BA%E4%BE%8B" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>示例</h4>
<p>已知两个线性表<code>La</code>和<code>Lb</code>分别表示两个集合A和B，先将A、B按值非递减排列归并到新的线性表<code>Lc</code>，然后求一个新的集合<code>A = A ∪ B</code></p>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#define LIST_INIT_SIZE 100
#define LIST_INCREAMENT 10
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;

typedef struct
{
    ElemType *elem; //表基址
    int length;     //表当前存储容量（字节数）
    int listsize;   //表长（特指元素个数）
} SqList;

//初始化当前表
Status InitList(SqList *L)
{
    L-&gt;elem = (ElemType *)malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L-&gt;elem)
    {
        printf(&quot;初始化失败\n&quot;);
        return FALSE;
    }
    L-&gt;length = 0;
    L-&gt;listsize = LIST_INIT_SIZE;
    return TRUE;
}

//插入元素(操作的表, 插入位置, 插入元素)
Status ListInsert(SqList *L, int i, ElemType e)
{
    ElemType *cur, *loc; //当前元素位置, 元素插入位置

    //判断插入位置是否有效
    if (i &lt; 1 || i &gt; L-&gt;length + 1)
    {
        printf(&quot;插入位置无效\n&quot;);
        return FALSE;
    }

    //判断顺序表容量已满，进行扩容
    if (L-&gt;listsize == L-&gt;length)
    {
        L-&gt;elem = (ElemType *)realloc(L-&gt;elem, (L-&gt;length++) * sizeof(ElemType));
        //如果扩容失败，提示并结束操作
        if (!L-&gt;elem)
        {
            printf(&quot;扩容失败\n&quot;);
            return FALSE;
        }
        L-&gt;length++;
    }

    //初始化*loc位置，使其指向插入位置在顺序表中的对应下标
    loc = L-&gt;elem + i - 1;

    //从后往前依次移动插入位置之后的所有元素 for(cur指向表中的最后一个元素, cur大于等于loc, cur递减)
    for (cur = L-&gt;elem + L-&gt;length - 1; cur &gt;= loc; cur--)
        // for先判断条件在运行，此时cur已经指向倒数第二个元素
        *(cur + 1) = *cur;

    //将e的值赋值给插入位置的元素
    *loc = e;
    L-&gt;length++;

    return TRUE;
}

//删除元素
Status ListDelete(SqList *L, int i, ElemType *e)
{
    ElemType *loc, *cur;
    if (i &lt; 1 || i &gt; L-&gt;length)
    {
        printf(&quot;位置有误\n&quot;);
        return FALSE;
    }
    loc = L-&gt;elem + i - 1; //需要删除的元素在内存中的位置
    *e = *loc;             //暂时保存被删除的元素以便恢复

    for (cur = loc + 1; cur &lt;= L-&gt;elem + L-&gt;length - 1; cur++)
        *(cur - 1) = *cur;
    L-&gt;length--;
    return TRUE;
}

//将线性表Lb中所有不在La中的元素插入到La中
Status ListCollection(SqList *La, SqList *Lb)
{
    ElemType *LaCur, *LbCur;

    //依次选择Lb中的元素
    for (LbCur = Lb-&gt;elem; LbCur &lt;= Lb-&gt;elem + Lb-&gt;length - 1; LbCur++)
    {
        //与La中的元素依次比对
        for (LaCur = La-&gt;elem; LaCur &lt;= La-&gt;elem + La-&gt;length - 1; LaCur++)
        {
            if (*LbCur == *LaCur)
                break;
            if (LaCur == La-&gt;elem + La-&gt;length - 1)
                ListInsert(La, La-&gt;length + 1, *LbCur); // ListInsert()中会将插入位置自动-1匹配到元素下标，所以此处应该+1
        }
        printf(&quot;\n&quot;);
    }

    return TRUE;
}

//归并，将线性表La和Lb中的元素按非递减排列（相等或递增）归并到Lc中
Status MergeList(SqList La, SqList Lb, SqList *Lc)
{
    ElemType a, b, c;
    a = b = 0;
    c = 1;

    int i = 0;
    int a_len = La.length, b_len = Lb.length;
    int Max;

    while (a &lt; a_len &amp;&amp; b &lt; b_len)
    {
        if (La.elem[a] &lt;= Lb.elem[b])
        {
            Max = La.elem[a];
            a++;
        }
        else
        {
            Max = Lb.elem[b];
            b++;
        }
        ListInsert(Lc, c, Max);
        c++;
    }

    //比较结束后，未完成归并的线性表继续进行归并
    while (b &lt; b_len)
    {
        ListInsert(Lc, c, Lb.elem[b]);
        b++;
        c++;
    }
    while (a &lt; a_len)
    {
        ListInsert(Lc, c, Lb.elem[b]);
        a++;
        c++;
    }

    return TRUE;
}

//遍历元素
void ListTraverse(SqList L)
{
    ElemType *cur = L.elem;
    for (; cur &lt;= L.elem + L.length - 1; cur++)
        printf(&quot;%d &quot;, *cur);
    printf(&quot;\n&quot;);
}

int main()
{
    SqList La, Lb, Lc;
    ElemType e = 10;
    int i;

    InitList(&amp;La); //初始化SqList La
    InitList(&amp;Lb); //初始化SqList Lb
    InitList(&amp;Lc); //初始化SqList Lc

    for (i = 1; i &lt;= 10; i++)
        ListInsert(&amp;La, i, e++);

    e = 12;
    for (i = 1; i &lt;= 10; i++)
        ListInsert(&amp;Lb, i, e++);

    ListTraverse(La);
    ListTraverse(Lb);
    printf(&quot;\n&quot;);

    MergeList(La, Lb, &amp;Lc);
    printf(&quot;\n&quot;);
    ListTraverse(Lc);
    printf(&quot;\n&quot;);

    ListCollection(&amp;La, &amp;Lb);
    ListTraverse(La);

    return 0;
}

</code></pre>
<h3><a id="%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E8%BF%90%E7%AE%97%E6%95%88%E7%8E%87%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>顺序表的运算效率分析</h3>
<h4><a id="%E6%8F%92%E5%85%A5%E6%93%8D%E4%BD%9C%E6%97%B6%E9%97%B4%E6%95%88%E7%8E%87%EF%BC%88%E5%B9%B3%E5%9D%87%E7%A7%BB%E5%8A%A8%E6%AC%A1%E6%95%B0%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>插入操作时间效率（平均移动次数）</h4>
<p>在插入元素时，假设原有<code>n</code>个元素，共有<code>n+1</code>个位置可供插入（原有元素与新元素），任意位置均有\(\dfrac 1 {n+1}\)的概率插入元素，在第<code>i</code>个元素的位置插入新元素需要移动<code>n-i+1</code>个元素，经过累加求和得出在任意位置插入元素所需要移动元素的平均次数</p>
\[E_{is} = \sum_{i=1}^{n+1} p_i(n - i + 1) = \dfrac{1}{n + 1}\sum_{i=1}^{n+1}(n - i + 1) = \dfrac n 2
\]
<h4><a id="%E5%88%A0%E9%99%A4%E6%93%8D%E4%BD%9C%E6%97%B6%E9%97%B4%E6%95%88%E7%8E%87%EF%BC%88%E5%B9%B3%E5%9D%87%E7%A7%BB%E5%8A%A8%E6%AC%A1%E6%95%B0%EF%BC%89" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>删除操作时间效率（平均移动次数）</h4>
<p>在删除元素时，假设原有<code>n</code>个元素，共有<code>n</code>个位置可供删除，任意元素均有\(\dfrac 1 n\)的概率被删除，删除第<code>i</code>个元素需要移动<code>n-i</code>个元素，经过累加求和得出在任意位置删除元素所需要移动元素的平均次数</p>
\[E_{dl} = \sum_{i=1}^n q_i (n-i) = \dfrac 1 n \sum_{i=1}^n (n-i) = \dfrac {n-1} 2 
\]
<p><strong>注意：</strong> 顺序表中插入元素、删除元素的元素平均移动次数差距微乎其微，可以视为插入元素与删除元素的元素平均移动次数为总元素数量的一半</p>
<h2><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E9%93%BE%E5%BC%8F%E8%A1%A8%E7%A4%BA%E5%92%8C%E5%AE%9E%E7%8E%B0" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的链式表示和实现</h2>
<h3><a id="%E9%93%BE%E8%A1%A8%E7%9A%84%E8%A1%A8%E7%A4%BA" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链表的表示</h3>
<h4><a id="%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E7%89%B9%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链式存储特点</h4>
<p>链式结构是线性结构的物理映像，投影为链式的存储，<strong>逻辑上相邻</strong>的数据元素<strong>不一定存储在物理上相邻</strong>的存储单元中</p>
<pre class="line-numbers"><code class="language-mermaid">graph LR
    head[0098H]--&gt;a[&quot;'a' | 201BH&quot;]--&gt;b[&quot;'b' | 1087H&quot;]--&gt;|&quot;···&quot;|z[&quot;'z' | NULL&quot;]
</code></pre>
<ul>
<li>每个存储结点包含两部分：数据域和指针域（链域）</li>
<li>链式结构的存储密度<strong>小于</strong>顺序结构（顺序结构没有指针部分）</li>
</ul>
<h5><a id="%E6%95%B0%E6%8D%AE%E5%9F%9F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>数据域</h5>
<p>存储数据元素信息</p>
<h5><a id="%E6%8C%87%E9%92%88%E5%9F%9F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>指针域</h5>
<p>存储直接后继存储位置</p>
<h4><a id="%E4%B8%8E%E9%93%BE%E5%BC%8F%E5%AD%98%E5%82%A8%E6%9C%89%E5%85%B3%E7%9A%84%E6%9C%AF%E8%AF%AD" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>与链式存储有关的术语</h4>
<h5><a id="%E7%BB%93%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>结点</h5>
<p>数据元素的存储映像，由数据域和指针域两部分组成</p>
<h5><a id="%E9%93%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链表</h5>
<p>n个结点由指针链组成一个链表，它是线性表的链式存储映像，称为线性表的链式存储结构</p>
<h5><a id="%E5%8D%95%E9%93%BE%E8%A1%A8%E3%80%81%E5%8F%8C%E9%93%BE%E8%A1%A8%E3%80%81%E5%A4%9A%E9%93%BE%E8%A1%A8%E3%80%81%E5%BE%AA%E7%8E%AF%E9%93%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>单链表、双链表、多链表、循环链表</h5>
<ul>
<li>结点只有一个指针域的链表，称为单链表或线性链表（<strong>只能从前往后单向查找元素</strong>）</li>
<li>有两个指针域的链表，称为双链表（<strong>可以从任意方向查找元素</strong>）</li>
<li>有多个指针域的链表，称为多链表</li>
<li>首尾相接的链表，称为循环链表</li>
</ul>
<h5><a id="%E5%A4%B4%E6%8C%87%E9%92%88%E3%80%81%E5%A4%B4%E7%BB%93%E7%82%B9%E5%92%8C%E9%A6%96%E5%85%83%E7%BB%93%E7%82%B9" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>头指针、头结点和首元结点</h5>
<ul>
<li>
<p>头指针：是指向链表中第一个结点（头结点或首元结点）的<strong>指针</strong>，是一个具体的地址（值），单链表可由一个头指针<strong>唯一确定</strong></p>
</li>
<li>
<p>头结点：是在链表内的<strong>首元结点之前</strong>附设的一个结点，数据域内值存放<strong>空表标志</strong>和<strong>表长</strong>等信息，让该链表的操作在<strong>空和非空时</strong> 始终保持一致（<strong>头指针保持一致</strong>）</p>
</li>
<li>
<p>首元结点：是指链表中存储线<strong>性表第一个数据元素</strong><code>a1</code>的结点</p>
</li>
</ul>
<h4><a id="%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E5%8D%95%E9%93%BE%E8%A1%A8%E5%AD%98%E5%82%A8%E7%BB%93%E6%9E%84" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>线性表的单链表存储结构</h4>
<pre class="line-numbers"><code class="language-c">typedef struct Lnode
{
    ElemType data; //数据域
    struct Lnode *next; //指针域
} Lnode, *LinkList;
//*LinkList为Lnode类型的指针
</code></pre>
<h3><a id="%E9%93%BE%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%92%8C%E6%93%8D%E4%BD%9C" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链表的实现和操作</h3>
<pre class="line-numbers"><code class="language-c">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#define LIST_INIT_SIZE 100
#define LIST_INCREAMENT 10
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int Status;

typedef struct Lnode
{
    ElemType data;
    struct Lnode *next;
} Lnode, *LinkList;

//初始化链表
void InitList(LinkList &amp;L)
{
    L = (Lnode *)malloc(sizeof(Lnode));
    if (!L)
    {
        printf(&quot;初始化失败&quot;);
        return;
    }
    L-&gt;next = NULL;
}

//销毁链表
void DestroyList(LinkList &amp;L)
{
    LinkList cur, next;
    cur = L; // cur指向头结点

    //当cur指向NULL时（链表的尾结点被销毁），循环结束
    while (cur != NULL)
    {
        next = cur-&gt;next; // next指向当前cur指向的结点中*next变量存储的地址，也就是下一个结点
        free(cur);        //释放当前cur指向的结点
        cur = next;       // cur指向下一个结点
    }
    L = NULL; //释放L存储的空间
}

//清空链表
void ClearList(LinkList L)
{
    LinkList cur, next;
    cur = L-&gt;next; // cur指向头结点中*next变量存储的地址，也就是首元结点

    //当cur指向NULL时（链表的尾结点被销毁），循环结束
    while (cur != NULL)
    {
        next = cur-&gt;next; // next指向当前cur指向的结点中*next变量存储的地址，也就是下一个结点
        free(cur);        //释放当前cur指向的结点
        cur = next;       // cur指向下一个结点
    }
    L-&gt;next = NULL; //将头结点中*next变量存储的地址清空
}

//判断链表是否为空
Status ListEmpty(LinkList L)
{
    if (!(L-&gt;next))
        return FALSE;
    return TRUE;
}

//获取链表长度
int ListLength(LinkList L)
{
    LinkList cur = L-&gt;next; //将cur置为首元结点
    int i = 0;              //用于计数

    while (!cur)
    {
        cur = cur-&gt;next;
        i++;
    }
    return i;
}

//获取序号为i的元素，并将其存储在*e中
Status GetElem(LinkList L, int i, ElemType *e)
{
    LinkList cur = L-&gt;next; //将cur置为首元结点
    int j;                  //用于计数，与i进行对比
    while (!cur &amp;&amp; j &lt; i)   //单链表结构是单向的，查找i的值需要定位到i的直接前驱，也就是i-1
    {
        j++;
        cur = cur-&gt;next;
    }
    if (cur)
        return FALSE;
    *e = cur-&gt;data;
    return TRUE;
}

//获取表中为e的元素，并返回序号值
int LocateElem(LinkList L, ElemType e)
{
    int i = 1;
    LinkList cur = L-&gt;next; //将cur置为首元结点

    while (!cur)
    {
        if (cur-&gt;data == e)
            return i;
        cur = cur-&gt;next;
        i++;
    }
    return FALSE;
}

//获取表中为cur_e的元素，并将它的前驱和后继存储在*e中
Status PriorElem(LinkList L, ElemType cur_e, ElemType *e)
{
    LinkList cur, pre;
    cur = L-&gt;next; //将cur置为首元结点
    while (cur != NULL)
    {
        pre = cur;
        cur = cur-&gt;next;
        if (!cur &amp;&amp; cur-&gt;data == cur_e)
        {
            *e = pre-&gt;data;
            return TRUE;
        }
    }
    return FALSE;
}
Status NextElem(LinkList L, ElemType cur_e, ElemType *e)
{
    LinkList cur, next;
    cur = L-&gt;next;
    while (!cur)
    {
        next = cur-&gt;next;
        if (!next &amp;&amp; cur-&gt;data == cur_e)
        {
            *e = next-&gt;data;
            return TRUE;
        }
        cur = next;
    }
    return FALSE;
}

//插入元素
void ListInsert(LinkList L, int i, ElemType e)
{
    LinkList cur, next;
    int p = 0;
    cur = L;                         //指向头结点
    while (cur != NULL &amp;&amp; p &lt; i - 1) // cur无后继可以进行追加
    {
        cur = cur-&gt;next;
        p++;
    }
    if (cur == NULL)
    {
        printf(&quot;位置不正确\n&quot;);
        return;
    }
    next = (LinkList)malloc(sizeof(Lnode));
    if (!next)
    {
        printf(&quot;空间分配失败\n&quot;);
        return;
    }
    next-&gt;data = e;
    next-&gt;next = cur-&gt;next;
    cur-&gt;next = next;
}

//删除元素
Status ListDelete(LinkList L, int i, ElemType *e)
{
    LinkList cur, next;
    int p = 0;
    cur = L;                               //指向头结点
    while (cur-&gt;next != NULL &amp;&amp; p &lt; i - 1) // cur无后继表示没有可删除的元素
    {
        cur = cur-&gt;next;
        p++;
    }
    if (cur == NULL)
    {
        printf(&quot;位置不正确&quot;);
        return FALSE;
    }
    next = cur-&gt;next;       // next指向需要删除的元素
    *e = next-&gt;data;        //将需要删除的结点的值存储在e中
    cur-&gt;next = next-&gt;next; //被删除元素的前驱的*next指向被删除元素的后继
    free(next);             //释放被删除的结点
    return TRUE;
}

//访问所有节点
void ListTraverse(LinkList L)
{
    LinkList cur = L-&gt;next;
    while (cur != NULL)
    {
        printf(&quot;%d&quot;, cur-&gt;data);
        cur = cur-&gt;next;
    }
    printf(&quot;\n&quot;);
}
int main()
{
    LinkList L;
    InitList(&amp;L);
    return 0;
}

</code></pre>
<h3><a id="%E9%93%BE%E8%A1%A8%E7%9A%84%E8%BF%90%E7%AE%97%E6%95%88%E7%8E%87%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>链表的运算效率分析</h3>
<h4><a id="%E6%97%B6%E9%97%B4%E6%95%88%E7%8E%87%E5%88%86%E6%9E%90" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>时间效率分析</h4>
<h5><a id="%E6%9F%A5%E6%89%BE" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>查找</h5>
<p>因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为O(n)</p>
<h5><a id="%E6%8F%92%E5%85%A5%E5%92%8C%E5%88%A0%E9%99%A4" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>插入和删除</h5>
<p>因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O(1)</p>
<h3><a id="%E5%85%B6%E5%AE%83%E9%93%BE%E8%A1%A8%E5%BD%A2%E5%BC%8F" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>其它链表形式</h3>
<h4><a id="%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>双向链表</h4>
<p>有两个指针域的链表，称为双链表</p>
<h4><a id="%E9%9D%99%E6%80%81%E9%93%BE%E8%A1%A8" class="anchor" aria-hidden="true"><span class="octicon octicon-link"></span></a>静态链表</h4>
<p>数组的一个分量表示一个结点，同时用游标代替指针指示结点在数组中的相对位置</p>

				</article>
				<div class="comments-wrap">
					<div class="share-comments">
						

						

						
					</div>
				</div><!-- end comments wrap -->
			</div>
		</div><!-- end columns -->
	</div><!-- end container -->
</section>  
<script type="text/javascript"
	src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.7/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/x-mathjax-config">MathJax.Hub.Config({TeX: { equationNumbers: { autoNumber: "AMS" } }});</script>










<script>!function(){var deflate=function(){var e,n,r,t,i,o,a,f,d,l,c,u,h,w,m,s,g,p,y,_,v,x,A,C,b,V,E,z,I,S,B,G,L,M,O,D,N,q,T,k,H,U,j,F,P,R,J,K,Q,W,X,Y,Z,$,ee,ne,re=32768,te=0,ie=1,oe=2,ae=6,fe=!0,de=32768,le=64,ce=8192,ue=2*re,he=3,we=258,me=16,se=8192,ge=se,pe=8192,ye=pe-1,_e=re-1,ve=0,xe=4096,Ae=we+he+1,Ce=re-Ae,be=1,Ve=15,Ee=7,ze=29,Ie=256,Se=256,Be=Ie+1+ze,Ge=30,Le=19,Me=16,Oe=17,De=18,Ne=2*Be+1,qe=parseInt((13+he-1)/he),Te=null;function ke(){this.fc=0,this.dl=0}function He(){this.dyn_tree=null,this.static_tree=null,this.extra_bits=null,this.extra_base=0,this.elems=0,this.max_length=0,this.max_code=0}function Ue(e,n,r,t){this.good_length=e,this.max_lazy=n,this.nice_length=r,this.max_chain=t}var je=[0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0],Fe=[0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13],Pe=[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7],Re=[16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15],Je=[new Ue(0,0,0,0),new Ue(4,4,8,4),new Ue(4,5,16,8),new Ue(4,6,32,32),new Ue(4,4,16,16),new Ue(8,16,32,32),new Ue(8,16,128,128),new Ue(8,32,128,256),new Ue(32,128,258,1024),new Ue(32,258,258,4096)];function Ke(){var n;return null!=e?(n=e,e=e.next):n=new function(){this.next=null,this.len=0,this.ptr=new Array(ce),this.off=0},n.next=null,n.len=n.off=0,n}function Qe(e){return c[re+e]}function We(e,n){return c[re+e]=n}function Xe(e){Te[o+i++]=e,o+i==ce&&function(){if(0!=i){var e,t;for(e=Ke(),null==n?n=r=e:r=r.next=e,e.len=i-o,t=0;t<e.len;t++)e.ptr[t]=Te[o+t];i=o=0}}()}function Ye(e){e&=65535,o+i<ce-2?(Te[o+i++]=255&e,Te[o+i++]=e>>>8):(Xe(255&e),Xe(e>>>8))}function Ze(){m=(m<<qe^255&f[v+he-1])&ye,s=Qe(m),c[v&_e]=s,We(m,v)}function $e(e,n){_n(n[e].fc,n[e].dl)}function en(e){return 255&(e<256?F[e]:F[256+(e>>7)])}function nn(e,n,r){return e[n].fc<e[r].fc||e[n].fc==e[r].fc&&U[n]<=U[r]}function rn(e,n,r){var t;for(t=0;t<r&&ne<ee.length;t++)e[n+t]=255&ee.charCodeAt(ne++);return t}function tn(e){var n,r,t=b,i=v,o=_,a=v>Ce?v-Ce:ve,d=v+we,l=f[i+o-1],u=f[i+o];_>=z&&(t>>=2);do{if(f[(n=e)+o]==u&&f[n+o-1]==l&&f[n]==f[i]&&f[++n]==f[i+1]){i+=2,n++;do{}while(f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&f[++i]==f[++n]&&i<d);if(r=we-(d-i),i=d-we,r>o){if(x=e,o=r,fe){if(r>=we)break}else if(r>=I)break;l=f[i+o-1],u=f[i+o]}}}while((e=c[e&_e])>a&&0!=--t);return o}function on(){var e,n,r=ue-C-v;if(-1==r)r--;else if(v>=re+Ce){for(e=0;e<re;e++)f[e]=f[e+re];for(x-=re,v-=re,w-=re,e=0;e<pe;e++)We(e,(n=Qe(e))>=re?n-re:ve);for(e=0;e<re;e++)n=c[e],c[e]=n>=re?n-re:ve;r+=re}A||((e=rn(f,v+C,r))<=0?A=!0:C+=e)}function an(){A||(u=0,h=0,function(){var e,n,r,t,i;if(0!=L[0].dl)return;for(O.dyn_tree=S,O.static_tree=G,O.extra_bits=je,O.extra_base=Ie+1,O.elems=Be,O.max_length=Ve,O.max_code=0,D.dyn_tree=B,D.static_tree=L,D.extra_bits=Fe,D.extra_base=0,D.elems=Ge,D.max_length=Ve,D.max_code=0,N.dyn_tree=M,N.static_tree=null,N.extra_bits=Pe,N.extra_base=0,N.elems=Le,N.max_length=Ee,N.max_code=0,r=0,t=0;t<ze-1;t++)for(P[t]=r,e=0;e<1<<je[t];e++)j[r++]=t;for(j[r-1]=t,i=0,t=0;t<16;t++)for(R[t]=i,e=0;e<1<<Fe[t];e++)F[i++]=t;for(i>>=7;t<Ge;t++)for(R[t]=i<<7,e=0;e<1<<Fe[t]-7;e++)F[256+i++]=t;for(n=0;n<=Ve;n++)q[n]=0;e=0;for(;e<=143;)G[e++].dl=8,q[8]++;for(;e<=255;)G[e++].dl=9,q[9]++;for(;e<=279;)G[e++].dl=7,q[7]++;for(;e<=287;)G[e++].dl=8,q[8]++;for(un(G,Be+1),e=0;e<Ge;e++)L[e].dl=5,L[e].fc=vn(e,5);ln()}(),function(){var e;for(e=0;e<pe;e++)c[re+e]=0;if(V=Je[E].max_lazy,z=Je[E].good_length,fe||(I=Je[E].nice_length),b=Je[E].max_chain,v=0,w=0,(C=rn(f,0,2*re))<=0)return A=!0,void(C=0);for(A=!1;C<Ae&&!A;)on();for(m=0,e=0;e<he-1;e++)m=(m<<qe^255&f[e])&ye}(),n=null,i=0,o=0,E<=3?(_=he-1,y=0):(y=he-1,p=0),a=!1)}function fn(e,r,i){var o;return t||(an(),t=!0,0!=C)?(o=dn(e,r,i))==i?i:a?o:(E<=3?function(){for(;0!=C&&null==n;){var e;if(Ze(),s!=ve&&v-s<=Ce&&(y=tn(s))>C&&(y=C),y>=he)if(e=gn(v-x,y-he),C-=y,y<=V){y--;do{v++,Ze()}while(0!=--y);v++}else v+=y,y=0,m=((m=255&f[v])<<qe^255&f[v+1])&ye;else e=gn(0,255&f[v]),C--,v++;for(e&&(sn(0),w=v);C<Ae&&!A;)on()}}():function(){for(;0!=C&&null==n;){if(Ze(),_=y,g=x,y=he-1,s!=ve&&_<V&&v-s<=Ce&&((y=tn(s))>C&&(y=C),y==he&&v-x>xe&&y--),_>=he&&y<=_){var e;e=gn(v-1-g,_-he),C-=_-1,_-=2;do{v++,Ze()}while(0!=--_);p=0,y=he-1,v++,e&&(sn(0),w=v)}else 0!=p?(gn(0,255&f[v-1])&&(sn(0),w=v),v++,C--):(p=1,v++,C--);for(;C<Ae&&!A;)on()}}(),0==C&&(0!=p&&gn(0,255&f[v-1]),sn(1),a=!0),o+dn(e,o+r,i-o)):(a=!0,0)}function dn(r,t,a){var f,d,l,c;for(f=0;null!=n&&f<a;){for((d=a-f)>n.len&&(d=n.len),l=0;l<d;l++)r[t+f+l]=n.ptr[n.off+l];var u;if(n.off+=d,n.len-=d,f+=d,0==n.len)u=n,n=n.next,(c=u).next=e,e=c}if(f==a)return f;if(o<i){for((d=a-f)>i-o&&(d=i-o),l=0;l<d;l++)r[t+f+l]=Te[o+l];f+=d,i==(o+=d)&&(i=o=0)}return f}function ln(){var e;for(e=0;e<Be;e++)S[e].fc=0;for(e=0;e<Ge;e++)B[e].fc=0;for(e=0;e<Le;e++)M[e].fc=0;S[Se].fc=1,Z=$=0,K=Q=W=0,X=0,Y=1}function cn(e,n){for(var r=T[n],t=n<<1;t<=k&&(t<k&&nn(e,T[t+1],T[t])&&t++,!nn(e,r,T[t]));)T[n]=T[t],n=t,t<<=1;T[n]=r}function un(e,n){var r,t,i=new Array(Ve+1),o=0;for(r=1;r<=Ve;r++)o=o+q[r-1]<<1,i[r]=o;for(t=0;t<=n;t++){var a=e[t].dl;0!=a&&(e[t].fc=vn(i[a]++,a))}}function hn(e){var n,r,t=e.dyn_tree,i=e.static_tree,o=e.elems,a=-1,f=o;for(k=0,H=Ne,n=0;n<o;n++)0!=t[n].fc?(T[++k]=a=n,U[n]=0):t[n].dl=0;for(;k<2;){var d=T[++k]=a<2?++a:0;t[d].fc=1,U[d]=0,Z--,null!=i&&($-=i[d].dl)}for(e.max_code=a,n=k>>1;n>=1;n--)cn(t,n);do{n=T[be],T[be]=T[k--],cn(t,be),r=T[be],T[--H]=n,T[--H]=r,t[f].fc=t[n].fc+t[r].fc,U[n]>U[r]+1?U[f]=U[n]:U[f]=U[r]+1,t[n].dl=t[r].dl=f,T[be]=f++,cn(t,be)}while(k>=2);T[--H]=T[be],function(e){var n,r,t,i,o,a,f=e.dyn_tree,d=e.extra_bits,l=e.extra_base,c=e.max_code,u=e.max_length,h=e.static_tree,w=0;for(i=0;i<=Ve;i++)q[i]=0;for(f[T[H]].dl=0,n=H+1;n<Ne;n++)(i=f[f[r=T[n]].dl].dl+1)>u&&(i=u,w++),f[r].dl=i,r>c||(q[i]++,o=0,r>=l&&(o=d[r-l]),a=f[r].fc,Z+=a*(i+o),null!=h&&($+=a*(h[r].dl+o)));if(0!=w){do{for(i=u-1;0==q[i];)i--;q[i]--,q[i+1]+=2,q[u]--,w-=2}while(w>0);for(i=u;0!=i;i--)for(r=q[i];0!=r;)(t=T[--n])>c||(f[t].dl!=i&&(Z+=(i-f[t].dl)*f[t].fc,f[t].fc=i),r--)}}(e),un(t,a)}function wn(e,n){var r,t,i=-1,o=e[0].dl,a=0,f=7,d=4;for(0==o&&(f=138,d=3),e[n+1].dl=65535,r=0;r<=n;r++)t=o,o=e[r+1].dl,++a<f&&t==o||(a<d?M[t].fc+=a:0!=t?(t!=i&&M[t].fc++,M[Me].fc++):a<=10?M[Oe].fc++:M[De].fc++,a=0,i=t,0==o?(f=138,d=3):t==o?(f=6,d=3):(f=7,d=4))}function mn(e,n){var r,t,i=-1,o=e[0].dl,a=0,f=7,d=4;for(0==o&&(f=138,d=3),r=0;r<=n;r++)if(t=o,o=e[r+1].dl,!(++a<f&&t==o)){if(a<d)do{$e(t,M)}while(0!=--a);else 0!=t?(t!=i&&($e(t,M),a--),$e(Me,M),_n(a-3,2)):a<=10?($e(Oe,M),_n(a-3,3)):($e(De,M),_n(a-11,7));a=0,i=t,0==o?(f=138,d=3):t==o?(f=6,d=3):(f=7,d=4)}}function sn(e){var n,r,t,i,o;if(i=v-w,J[W]=X,hn(O),hn(D),t=function(){var e;for(wn(S,O.max_code),wn(B,D.max_code),hn(N),e=Le-1;e>=3&&0==M[Re[e]].dl;e--);return Z+=3*(e+1)+5+5+4,e}(),(r=$+3+7>>3)<=(n=Z+3+7>>3)&&(n=r),i+4<=n&&w>=0)for(_n((te<<1)+e,3),xn(),Ye(i),Ye(~i),o=0;o<i;o++)Xe(f[w+o]);else r==n?(_n((ie<<1)+e,3),pn(G,L)):(_n((oe<<1)+e,3),function(e,n,r){var t;for(_n(e-257,5),_n(n-1,5),_n(r-4,4),t=0;t<r;t++)_n(M[Re[t]].dl,3);mn(S,e-1),mn(B,n-1)}(O.max_code+1,D.max_code+1,t+1),pn(S,B));ln(),0!=e&&xn()}function gn(e,n){if(l[K++]=n,0==e?S[n].fc++:(e--,S[j[n]+Ie+1].fc++,B[en(e)].fc++,d[Q++]=e,X|=Y),Y<<=1,0==(7&K)&&(J[W++]=X,X=0,Y=1),E>2&&0==(4095&K)){var r,t=8*K,i=v-w;for(r=0;r<Ge;r++)t+=B[r].fc*(5+Fe[r]);if(t>>=3,Q<parseInt(K/2)&&t<parseInt(i/2))return!0}return K==se-1||Q==ge}function pn(e,n){var r,t,i,o,a=0,f=0,c=0,u=0;if(0!=K)do{0==(7&a)&&(u=J[c++]),t=255&l[a++],0==(1&u)?$e(t,e):($e((i=j[t])+Ie+1,e),0!=(o=je[i])&&_n(t-=P[i],o),$e(i=en(r=d[f++]),n),0!=(o=Fe[i])&&_n(r-=R[i],o)),u>>=1}while(a<K);$e(Se,e)}var yn=16;function _n(e,n){h>yn-n?(Ye(u|=e<<h),u=e>>yn-h,h+=n-yn):(u|=e<<h,h+=n)}function vn(e,n){var r=0;do{r|=1&e,e>>=1,r<<=1}while(--n>0);return r>>1}function xn(){h>8?Ye(u):h>0&&Xe(u),u=0,h=0}return function(i,o){var a,u;ee=i,ne=0,void 0===o&&(o=ae),function(i){var o;if(i?i<1?i=1:i>9&&(i=9):i=ae,E=i,t=!1,A=!1,null==Te){for(e=n=r=null,Te=new Array(ce),f=new Array(ue),d=new Array(ge),l=new Array(de+le),c=new Array(1<<me),S=new Array(Ne),o=0;o<Ne;o++)S[o]=new ke;for(B=new Array(2*Ge+1),o=0;o<2*Ge+1;o++)B[o]=new ke;for(G=new Array(Be+2),o=0;o<Be+2;o++)G[o]=new ke;for(L=new Array(Ge),o=0;o<Ge;o++)L[o]=new ke;for(M=new Array(2*Le+1),o=0;o<2*Le+1;o++)M[o]=new ke;O=new He,D=new He,N=new He,q=new Array(Ve+1),T=new Array(2*Be+1),U=new Array(2*Be+1),j=new Array(we-he+1),F=new Array(512),P=new Array(ze),R=new Array(Ge),J=new Array(parseInt(se/8))}}(o);for(var h=new Array(1024),w=[];(a=fn(h,0,h.length))>0;){var m=new Array(a);for(u=0;u<a;u++)m[u]=String.fromCharCode(h[u]);w[w.length]=m.join("")}return ee=null,w.join("")}}();function encode64(e){for(r="",i=0;i<e.length;i+=3)i+2==e.length?r+=append3bytes(e.charCodeAt(i),e.charCodeAt(i+1),0):i+1==e.length?r+=append3bytes(e.charCodeAt(i),0,0):r+=append3bytes(e.charCodeAt(i),e.charCodeAt(i+1),e.charCodeAt(i+2));return r}function append3bytes(e,n,t){return c1=e>>2,c2=(3&e)<<4|n>>4,c3=(15&n)<<2|t>>6,c4=63&t,r="",r+=encode6bit(63&c1),r+=encode6bit(63&c2),r+=encode6bit(63&c3),r+=encode6bit(63&c4),r}function encode6bit(e){return e<10?String.fromCharCode(48+e):(e-=10)<26?String.fromCharCode(65+e):(e-=26)<26?String.fromCharCode(97+e):0==(e-=26)?"-":1==e?"_":"?"}function insertAfter(e,n){e.parentNode.insertBefore(n,e.nextSibling)}var mwebChartEleId="mweb-chart-ele-",glNumber=0;function drawOldSeq(e,n){Diagram.parse(n).drawSVG(e,{theme:"simple"})}function drawOldFlow(e,n){flowchart.parse(n).drawSVG(e)}function drawMermaid(e,n){var r=document.getElementById(e);r.className="mermaid",r.innerHTML=n}function drawPlantUML(e,n){var r=document.getElementById(e),t=unescape(encodeURIComponent(n)),i="https://www.plantuml.com/plantuml/svg/"+encode64(deflate(t,9));r.innerHTML='<a target="_blank" href="'+i+'"><img src="'+i+'" /></a>'}function drawViz_circo(e,n){(new Viz).renderSVGElement(n,{engine:"circo"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_dot(e,n){(new Viz).renderSVGElement(n,{engine:"dot"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_fdp(e,n){(new Viz).renderSVGElement(n,{engine:"fdp"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_neato(e,n){(new Viz).renderSVGElement(n,{engine:"neato"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_osage(e,n){(new Viz).renderSVGElement(n,{engine:"osage"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawViz_twopi(e,n){(new Viz).renderSVGElement(n,{engine:"twopi"}).then(function(n){document.getElementById(e).appendChild(n)})}function drawECharts(eleIID,txt){var ele=document.getElementById(eleIID);try{eval(txt);var myoption=option;myoption.animation=!1,void 0!==myoption.width?ele.style.width=myoption.width+10+"px":ele.style.width="100%",void 0!==myoption.height?ele.style.height=myoption.height+10+"px":ele.style.height="350px";var myChart=echarts.init(ele);myChart.setOption(myoption)}catch(e){}}var init=function(){var e=[[".language-plantuml",drawPlantUML]];"undefined"!=typeof Diagram&&e.push([".language-sequence",drawOldSeq]),"undefined"!=typeof flowchart&&e.push([".language-flow",drawOldFlow]),"undefined"!=typeof mermaid&&e.push([".language-mermaid",drawMermaid]),"undefined"!=typeof Viz&&(e.push([".language-circo",drawViz_circo]),e.push([".language-dot",drawViz_dot]),e.push([".language-fdp",drawViz_fdp]),e.push([".language-neato",drawViz_neato]),e.push([".language-osage",drawViz_osage]),e.push([".language-twopi",drawViz_twopi])),"undefined"!=typeof echarts&&e.push([".language-echarts",drawECharts]);for(var n=0;n<e.length;n++)for(var r=e[n][0],t=e[n][1],i=document.querySelectorAll(r),o=0;o<i.length;o++){var a=i[o],f=a.innerText||a.textContent;a=a.parentElement;var d=document.createElement("div"),l=mwebChartEleId+glNumber;glNumber++,d.innerHTML='<div id="'+l+'"></div>',insertAfter(a,d),a.parentElement.removeChild(a),t(l,f)}"undefined"!=typeof mermaid&&mermaid.initialize({startOnLoad:!0})};document.addEventListener("DOMContentLoaded",function(e){init()})}();</script>



<link rel="stylesheet" type="text/css"
	href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/4.7.0/css/font-awesome.min.css" />
<script src="https://cdnjs.cloudflare.com/ajax/libs/mermaid/8.4.3/mermaid.min.js"></script>




<script src="asset/prism.js"></script>









</body>

</html>